import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class LeetCode {
    public int widthOfBinaryTree(TreeNode root) {
        List<Pair<TreeNode,Integer>> p = new ArrayList<>();
        p.add(new Pair<>(root,1));
        int ret = 0;
        while(!p.isEmpty()){
            Pair<TreeNode,Integer> t1 = p.get(0);
            Pair<TreeNode,Integer> t2 = p.get(p.size()-1);
            ret = Math.max(ret,t2.getValue()-t1.getValue()+1);

            List<Pair<TreeNode,Integer>> tmp = new ArrayList<>();
            for(Pair<TreeNode,Integer> t:p){
                TreeNode node = t.getKey();
                int k = t.getValue();
                if(node.left!=null){
                    tmp.add(new Pair<>(node.left,2*k));
                }
                if(node.right!=null){
                    tmp.add(new Pair<>(node.right,2*k+1));
                }
            }
            p = tmp;
        }
        return ret;
    }
}
